大家一定會寫的題目，因為是第一題 XD。今天會知道選擇適合資料結構解決問題是非常重要的，但要如何選擇? 前提就是要對資料結構概念跟寫法需要有一定熟悉程度
/*
Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
Example:
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1]
*/
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var twoSum = function(nums, target) {
};
var twoSum = function(nums, target) {
const len = nums.length;
for(let i = 0; i< len; i++ ){
var ind = nums.indexOf(target - nums[i]);
if(ind !== -1 && i !== ind){
return [i, ind];
}
}
};
用這個方法時間複雜度大於 Big (n²)，因為 for 一次，indexOf 基本上也是再遍歷一次。難怪 Runtime: faster than 18.49% of JavaScript online submissions for Two Sum.
其實概念跟之前大同小異，只是不同語法，效能就差很多。
var twoSum = function(nums, target) {
let lookup = new Map();
for(const [index, val] of nums.entries()){
if(lookup.has(target - val)){
return [index, lookup.get(target - val)]
}
lookup.set(val, index)
}
};
Runtime: 52 ms, faster than 92.70% of JavaScript online submissions for Two Sum.
分數從 18 瞬間到 92，所以說選擇適合資料結構解決問題是非常重要的
歡迎追蹤我的部落格，除了技術文也會分享一些在矽谷工作的甘苦。
這個例子中，使用 Map 的效率感覺明顯會比使用 Array 快上許多，但因為 Map.prototype.has 跟 Map.prototype.get 在時間複雜度上都還是 Big O(n) 的操作。如果跟使用 Object 當作映射用的 mapping 表似乎又會比 Map 快一點！？直接用 Object 的 key 取的資料的時間複雜度應該為 Big O(1)？
以下是我在 Leetcode 上的測試：
第三個是使用 hannahpun 大大提供的 Map 解，另外兩個是都是使用 Object 去存放對應的資料並在需要時取出使用，差別在於第一種（如下）是使用 typeof map[indValue] !== 'undefined' 而第二種在判斷時是使用 Object.prototype.hasOwnProperty 去判斷鍵值是否存在：
var twoSum = function(nums, target) {
const map = {}
let result
nums.forEach((item, index) => {
let indValue = target - item;
if(typeof map[indValue] !== 'undefined') {
result = [map[indValue], index]
}
map[item] = index
})
return result
}
不過測試數次過後，感覺上面給的時間真的只能當參考，每次都不一樣。就算同樣的 code 都可以在71.41% - 98.10% 之間來回了
"不過測試數次過後，感覺上面給的時間真的只能當參考，每次都不一樣。就算同樣的 code 都可以在 71.41% - 98.10% 之間來回了"
自己測過其他題目時也剛好有觀察到這樣的現象
var twoSum = function(nums, target) {
const m = new Map();
let result;
nums.forEach( (item, index) => {
let indValue = target - item;
if (m.has(indValue)) {
result = [m.get(indValue), index];
}
m.set(item, index);
})
return result;
};
是否在有答案時就可以跳出 loop 了
iThome鐵人賽
看影片追技術